package com.liuwei.spring.cloud.junit.leetcode.array;

import lombok.extern.slf4j.Slf4j;
import org.apache.commons.lang3.ArrayUtils;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/jump-game-ii/?envType=study-plan-v2&envId=top-interview-150
 */
@Slf4j
public class JumpGameMin {

    public static void main(String[] args) {
        JumpGameMin instance = new JumpGameMin();
        int[] nums = {3,0,6,1,5};
        //int[] nums = {3,2,1,0,4};
//        int[] nums = {1,2,3};
//        int jumped = instance.jump(nums);
//        System.out.println("jumped:"+jumped);

//        Arrays.sort(nums);
//        log.info("{}", Arrays.toString(nums));
//        ArrayUtils.reverse(nums);
//        log.info("{}", Arrays.toString(nums));
        System.out.println("hindex:"+instance.hIndex(nums));
    }

    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < citations.length; i++) {
            int count = i+1;
            if(citations[citations.length-1-i]>=count){
                if(max<=count){
                    max = count;
                }
            }
        }
        return max;
    }

    public int jump(int[] nums) {
        return jump(nums,nums.length-1);
    }

    public int jump(int[] nums,int target) {
        if(target==0){
            return 0;
        }
        int minSteps = Integer.MAX_VALUE;
        for (int i = 0; i < target; i++) {
            int temp = nums[i];
            if(i+temp>=target){
                int step = jump(nums,i);
                if(step+1<=minSteps){
                    minSteps = step+1;
                }
            }
        }
        return minSteps;
    }

}
